"""
题目：https://leetcode-cn.com/problems/trapping-rain-water/
    给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
    示例1：
    输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
    输出：6
    解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 
方法：动态规划
时间复杂度：O(n)
空间复杂度：O(n)
"""


class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        n = len(height)
        #leftMax表示从左至右的顺序中，当前位置i的柱子最大高度，它的取值是从位置i-1的最大高度同当前位置的高度进行对比，并取最大值进行保存。

        leftMax = [0] * n
        #rightMax表示从右至左的顺序中，当前位置i的柱子最大高度，它的取值是从位置i+1的最大高度同当前位置的高度进行对比，并取最大值进行保存。

        rightMax = [0] * n

        #在计算leftMax时，我们需要从左至右对height进行遍历，而leftMax第一个位置得值就是height第一个位置得值
        leftMax[0] = height[0]

        #在计算rightMax时，我们需要从右至左对height进行遍历，而rightMax最后一个位置得值就是height最后一个位置得值
        rightMax[n-1] = height[n - 1]

        for i in range(1,n):
            leftMax[i] = max(leftMax[i - 1],height[i])

        for i in range(n-2,-1,-1):
            rightMax[i] = max(rightMax[i + 1],height[i])
        
        res = []
        #此处遍历height中得每一个位置得值，而当前位置能保存得最大雨水，是其leftMax和rightMax得最小值同height[i]之间得差值。
        for i in range(n):
            res.append(abs(min(leftMax[i],rightMax[i]) - height[i]))
        # print(res)
        return sum(res)